package backTracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author pengfei.hpf
 * @date 2020/3/18
 * @verdion 1.0.0
 */
public class PalindromePartitioning {

//    public List<List<String>> partition(String s){
//        if(s == null || s.length() == 0){
//            return new LinkedList<>();
//        }
//        char[] chars = s.toCharArray();
//        return divide(chars, 0, chars.length - 1);
//    }
//
//    public List<List<String>> divide(char[] chars, int start, int end){
//        List<List<String>> res = new LinkedList<>();
//        if(start > end){
//            res.add(new LinkedList<>());
//            return res;
//        }
//        if(start == end){
//            List<String> list = new LinkedList<>();
//            list.add(String.valueOf(chars[start]));
//            res.add(list);
//            return res;
//        }
//        for(int i = start; i <= end; i ++){
//            if(isPalindrome(chars, start, i)){
//                List<List<String>> rest = divide(chars, i+1, end);
//                String t = String.valueOf(chars, start, i - start + 1);
//                for(List<String> list: rest){
//                    list.add(0,t);
//                }
//                res.addAll(rest);
//            }
//        }
//        return res;
//    }
//
//    private boolean isPalindrome(char[] chars, int l, int r){
//        while(l < r){
//            if(chars[l] != chars[r]){
//                return false;
//            }
//            l ++;
//            r --;
//        }
//        return true;
//    }

    // 带备忘录!!
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s){
        if(s == null){
            return res;
        }
        char[] chars = s.toCharArray();
        int[][] dp = new int[chars.length][chars.length];
        divide(chars, 0, new Stack<>(), dp);
        return res;
    }
    public void divide(char[] chars, int start, Stack<String> path, int[][] dp){
        if(start == chars.length){
            List<String> list = new ArrayList<>(path);
            res.add(list);
            return;
        }
        for(int i = start; i < chars.length; i ++){
            if(isPalindrome(chars, start, i, dp)){
                String t = String.valueOf(chars, start, i - start + 1);
                path.push(t);
                divide(chars, i+1, path, dp);
                path.pop();
            }
        }
    }

    private boolean isPalindrome(char[] chars, int l, int r, int[][] dp){
        if(dp[l][r] == 0){

            while(l < r){
                if(chars[l] != chars[r]){
                    dp[l][r] = -1;
                    return false;
                }
                l ++;
                r --;
            }
            dp[l][r] = 1;
        }

        return dp[l][r] == 1;
    }
}
